%~ \chapter{Ecuaciones o Lineales en una variable}
\chapter{Ceros de Funciones}

Dada una funci\'on $f$, se desean hallar los valores $x$ para los 
cuales $f(x) = 0$, es decir los \textsl{ceros} de $f$. 
Existen m\'etodos iterativos que permiten hallar las ra\'ices de 
funciones no lineales. 
En general, para algoritmos iterativos, deben determinarse criterios 
de parada y calcularse el orden de convergencia.

\section{Orden de convergencia}

\begin{definition}
	Sean $\{\beta_n\}$ y $\{\alpha_n\}$ sucesiones tales que 
	$\displaystyle \lim_{n \rightarrow \infty}{\beta_n \rightarrow 0}$, 
	$\displaystyle \lim_{n \rightarrow \infty}
	{\alpha_n \rightarrow \alpha}$, si $\displaystyle \exists 
	\; k \in R, \: k > 0$ tal que \\
	$\displaystyle |\alpha_n - \alpha| \leq k \: |\beta_n|$ 
	$\rightarrow$ se dice que la sucesi\'on $\{\alpha_n\}$ 
	tiene orden de convergencia $O(\beta_n).$
\end{definition}

\begin{definition}
	Sea $\{x_n\}$ una sucesi\'on tal que $\displaystyle 
	\lim_{n \rightarrow \infty}{x_n \rightarrow x^{*}}$, si vale que 
		\begin{itemize}
			\item $\displaystyle |x_{n+1} - x^{*}| \leq k \: 
				{|x_n - x^{*}|}^{p}$ $\rightarrow$ la convergencia es 
				de orden $p$, $p \geq 1$.
			\item $\displaystyle \lim_{n \rightarrow \infty} 
				\frac{|x_{n+1} - x^{*}|}{{|x_n - x^{*}|}^{p}} = c$ 
				donde $c$ es una constante no nula $\rightarrow$ 
				a convergencia es de orden $p$.
		\end{itemize}	
		\textbf{Casos Particulares de Convergencia} $p = 1$ Lineal, 
			$1 < p < 2$ Superlineal, $p = 2$ Cuadr\'atica.
\end{definition}

\section{Criterios de parada}

Hay distintos criterios de parada para un algoritmo iterativo de 
b\'usqueda de ceros, ninguno de ellos lo suficientemente seguro. 
Tienden a ser preferibles los que utilizan el error relativo en lugar 
del absoluto, se los suele combinar con el l\'imite a la cantidad de iteraciones.

\begin{itemize}
%\setlength{\itemsep}{0pt}
	\item{$\displaystyle |x_n - x_{n-1}| < \varepsilon$}, la diferencia 
			entre dos soluciones es menor a $\varepsilon$.
	\item{$\displaystyle \frac{|x_n - x_{n-1}|}{|x_n|} < \varepsilon$}, 
			la diferencia \emph{relativa} entre dos soluciones 
			es menor a $\varepsilon$.
	\item{$\displaystyle |f(x_n)| < \varepsilon$}, el valor de la 
			funci\'on est\'a a distancia $\varepsilon$ de cero.
	\item{$\displaystyle |f(x_n) - f(x_{n-1})|< \varepsilon$}, la 
			diferencia absoluta entre dos iteraciones consecutivas 
			es menor a $\varepsilon$.
	\item{$\displaystyle \frac{|f(x_n) - f(x_{n-1})|}
			{|f(x_n)|}< \varepsilon$}, la diferencia \emph{relativa} 
			entre dos iteraciones consecutivas es menor a $\varepsilon$.
	\item{$\displaystyle \#\textrm{iters} > k$}, limite en la 
			cantidad de iteraciones.
\end{itemize}

Un caso problem\'atico t\'ipico es la serie geom\'etrica, que tiende 
a cero, aunque no s\'olo no tiene ra\'ices sino que incluso diverge.

\section{M\'etodo de Bisecci\'on}

Es un m\'etodo de b\'usqueda binaria, basado en el Teorema de 
Bolzano-Weierstrass. 
Requiere solamente continuidad de la funci\'on y dos puntos iniciales 
$a$ y $b$ tales que el signo de la funci\'on sea distinto en los dos 
puntos. 
Su convergencia, si bien es lineal, est\'a garantizada. 
Tiende a usarse para aproximarse a un entorno de la soluci\'on para 
luego utilizar m\'etodos m\'as veloces que requieren de un intervalo 
inicial m\'as acotado.

\paragraph{}
Dados $a$ y $b$ con las condiciones mencionadas, se divide el intervalo 
por el punto intermedio $\displaystyle c = \frac{b - a}{2}$. \\
Para la siguiente iteraci\'on se usar\'an los puntos $\{a, c\}$ si vale 
que $f(a)f(c) < 0$ y $\{c,b\}$ si en cambio se cumple $f(c)f(b) < 0$.
La idea es, al igual que en la b\'usqueda binaria, reducir a la mitad 
el intervalo en cada paso.

El error en el paso $i$ es 
$\displaystyle \varepsilon_i = |p_i - p| \leq \frac{b-a}{2^i}$.

\section{M\'etodo de Punto fijo}

Los problemas de b\'usqueda de ra\'ices y los de punto fijo son 
equivalentes, ya que para $p$ tal que $f(p)=0$, puede definirse 
una funci\'on $g$ con un punto fijo en $p$, por ej. $g(x) = x-f(x)$, 
de manera tal que cuando $p$ es punto fijo de $g$, 
tambi\'en es ra\'iz de $f$.

\begin{theorem}
	Sea $g$ una funci\'on es continua en $[a,b]$ tal que $g(x)$ 
	pertenece a $[a,b] \; \forall \; x \in [a,b]$, entonces $g$ 
	tiene un punto fijo en $[a,b]$. 
	Si adem\'as $g^{\prime}(x) \; \exists$ y 
	$|g^{\prime}(x)|\leq k < 1 \; \forall \; x \in (a,b)$, 
	entonces el punto fijo en $[a,b]$ es \'unico.
\end{theorem}

Para aproximar el punto fijo de una funci\'on $g$ se define la 
sucesi\'on $p_n = g(p_{n-1})$. Si esta sucesi\'on converge, lo hace 
al punto fijo. 
En la figura se puede ver el comportamiento de la iteraci\'on de punto 
fijo para varias funciones, algunas divergentes y otras convergentes.

\begin{figure}[H] \centering
	\subfloat{\includegraphics[scale=.20]{images/puntofijo_1.png}}
	\subfloat{\includegraphics[scale=.20]{images/puntofijo_2.png}}
	\subfloat{\includegraphics[scale=.20]{images/puntofijo_3.png}}
	\subfloat{\includegraphics[scale=.20]{images/puntofijo_4.png}}	
	\caption{Convergencia de punto fijo.}
	\label{newton}
\end{figure}

\begin{theorem}
	Sea $g$ una funci\'on es continua en $[a,b]$ tal que $g(x)$ 
	pertenece a $[a,b] \; \forall \; x \in [a,b]$, y $g^{\prime}(x) \; 
	\exists$ con $|g^{\prime}(x)|\leq k < 1 \; \forall \; x \in (a,b)$, 
	entonces para cualquier valor inicial $p_0 \in [a,b]$, la 
	sucesi\'on de punto fijo converge al \'unico punto fijo 
	$p$ en $[a,b]$.
\end{theorem}

\begin{corollary}
	El error absoluto del paso $i$ es 
	$|p_i - p| \leq k^i*max(p_0 - a, b - p_0)$.
	La convergencia puedde ser mon\'otona o alternante.
\end{corollary}

\begin{remark}
	Si $0 < g^{\prime}(x) < 1$ entonces si $p_0$ est\'a a la derecha 
	(o izquierda respectivamente) del punto fijo, siempre converge por 
	la derecha (o izquierda respectivamente). 
	Si $g^{\prime}(x)<0$, converge alternadamente, y el punto 
	fijo est\'a \textsl{dentro}.
\end{remark}

\begin{theorem}
	Si la iteraci\'on de punto fijo converge, 
	$g(x) \in C^k$, $g^{\prime}(p)=g^{\prime \prime}(p)= \dots = 
	g^{(k-1)}(p)=0$ y $g^{(k)}(p) \neq 0$ entonces $p_{n+1} = 
	g(p_n)$ tiene orden de convergencia $k$.
\end{theorem}

\section{M\'etodo de Newton-Raphson}
El m\'etodo de Newton-Rhapson es muy usado en la resoluci\'on de 
ecuaciones no lineales. 
Las hip\'otesis son mucho m\'as fuertes que para el m\'etodo de 
bisecci\'on pero la velocidad de convergencia es mucho mayor que en 
el m\'etodo de bisecci\'on. \\

\textbf{Derivaci\'on por convergencia cuadr\'atica:} 
\par
Sea la funci\'on generica de punto fijo 
$\displaystyle g(x)=x - h(x)f(x)$, se desean hallar los ceros de $f(x)$. 

Si se pide que $h(x) \neq 0$ entonces 
$g(x) = x \leftrightarrow f(x) = 0$. 
$$g^{\prime}(x)=1-h^{\prime}(x)f(x)-f^{\prime}(x)h(x)$$

\par
Como $f(x)=0$, se tiene $g^{\prime}(x)=1-f^{\prime}(x)h(x)$

\paragraph{}
Para que la convergencia sea al menos cuadr\'atica, se pide que la 
derivada de $g$ sea cero en el punto fijo $p$, \\
es decir $g^{\prime}(p) = 0$, entonces $\displaystyle 1 - 
f^{\prime}(p)h(p) = 0 \rightarrow h(p) = \frac{1}{f^{\prime}(p)}$

\par
Entonces con $\displaystyle h(x) = \frac{1}{f^{\prime}(x)}$ se cumplen 
las condiciones; el punto fijo de $g$ es raiz de $f$ y como la 
derivada en $p$ es cero, la convergencia es cuadr\'atica.

\begin{property}
	Sea $f$ una funci\'on, $f \in C^2[a,b]$, $f(p)=0$, 
	$f^{\prime}(p)\neq 0$ entonces existe $\delta >0$ tal que si $p_0$ 
	est\'a en el intervalo $[p-\delta,p+\delta]$, la sucesi\'on de 
	Newton $\displaystyle x_{n+1} = x_n - 
	\frac{f(x_n)}{f^{\prime}(x_n)}$ converge a $p$ cuadraticamente.
\end{property}

%~ Gr\'aficamente, como puede apreciarse en la figura. 
La aproximaci\'on se obtiene usando tangentes sucesivas. 
Comenzando con la aproximaci\'on inicial $p_0$, la siguiente 
aproximaci\'on $p_1$ es la intersecci\'on con el eje x de la l\'inea 
tangente a la gr\'afica de $f$ en $(p_0, f(p_0))$, y as\'i 
sucesivamente.

\begin{figure}[H] \centering
	\subfloat{\includegraphics[scale=.30]{images/newton.png}}
	\caption{Convergencia del m\'etodo de Newton-Rhapson.}
	\label{newton}
\end{figure}

\textbf{Derivaci\'on por Taylor:}
\par
Otra forma de obtener la sucesi\'on de Newton es mediante el polinomio 
de Taylor de grado 1 de $f(x)$. 
Sea $p$ ra\'iz de la funci\'on $f$, y $p^*$ una aproximaci\'on de $p$,
tal que $f(p^*) \neq 0$ y $|p^* - p|$ es lo suficientemente pequeño, 
entonces
$$f(x) = f(p^*) + f^{\prime}(p^*)(x-p^*) + 
					f^{\prime \prime}(\xi(x))\frac{(x-p^*)^2}{2!}$$ 

Como $|p^*-p|$ es pequeño, al elevarlo al cuadrado queda m\'as 
pequeño a\'un y por lo tanto puede omitirse el \'ultimo t\'ermino. 
Por lo tanto, $0 = f(p^*) + (p-p^*)f^{\prime}(p^*)$.

\paragraph{}
Despejando $p$ de la ecuaci\'on se obtiene la iteraci\'on de Newton 
$\displaystyle p = p^*-\frac{f(p^*)}{f^{\prime}(p^*)}$

\paragraph{}
La suposici\'on de que $|p^* - p|$ es suficientemente es falsa si 
$p^*$ no est\'a lo suficientemente cerca de $p$, pudiendo causar 
la divergencia del m\'etodo. 
En la demostraci\'on de la convergencia del m\'etodo, puede verse que 
el valor de la constante $k$ que acota a la derivada indica la rapidez 
de convergencia, disminuyendo a cero a medida que el procedimiento 
avanza.

\paragraph{}
El m\'etodo de Newton es muy poderoso, pero presenta un grave problema: 
la necesidad de conocer el valor de la derivada de $f$ en cada 
aproximaci\'on, lo cual con frecuencia puede ser un c\'alculo complejo 
con muchas operaciones o ser un dato no disponible, ya que quiz\'as ni 
siquiera se conoce la forma anal\'itica de la funci\'on.

\section{M\'etodo de la secante}

Este m\'etodo surge como una variante de Newton-Raphson, eliminando la 
necesidad de calcular la derivada de $f$ en cada iteraci\'on. 
La derivada es aproximada mediante cociente incremental. 
Se poseen dos aproximaciones iniciales $p_0$ y $p_1$, y luego, la 
aproximaci\'on $p_2$ es la intersecci\'on en $x$ de la recta secante 
que une $(p_0, f(p_0))$ y $(p_1,f(p_1))$. 
$p_3$ ser\'a la intersecci\'on de la recta que une $(p_1,f(p_1))$ y 
$(p_2,f(p_2))$ y as\'i sucesivamente. 

%~ \paragraph{}
%~ La f\'ormula de iteraci\'on es: 
\begin{equation}
	X_n=X_{n-1} - f(X_{n-1}) \underbrace{\frac{X_{n-1}-X_{n-2}}
	{f(X_{n-1})-f(X_{n-2})}}_{\textrm{aproximaci\'on de }f'(x)^{-1}}
\end{equation}

La ventaja de este m\'etodo es que no hay necesidad de la derivada, 
pero esto ocasiona que la velocidad de convergencia sea m\'as lenta 
que en el m\'etodo de Newton: es superlineal. 

Cuando $f(X_n)$ y $f(X_{n-1})$ se parecen mucho, la resta ocasiona 
problemas num\'ericos ya que se est\'a trabajando con aritm\'etica 
finita.

\section{M\'etodo Regula Falsi}

El m\'etodo de Regula Falsi genera aproximaciones del mismo modo que 
el de la secante, pero en cada paso se asegura que la ra\'iz quede 
entre dos iteraciones sucesivas.
%~ \par
Primero se poseen dos aproximaciones iniciales $p_0$ y $p_1$ con 
$f(p_0)f(p_1) < 0$. 
La aproximaci\'on $p_2$ se determina de la misma manera que para el 
m\'etodo de la secante: como la intersecci\'on en x de la l\'inea 
que une $(p_0,f(p_0))$ y $(p_1,f(p_1))$. 

\par
Para decidir con cu\'al secante calcular $p_3$ se eval\'ua si 
$f(p_2)f(p_1) < 0$.
%~ \par
Si esto se cumple, $p_1$ y $p_2$ encierran un ra\'iz, entonces 
$p_3$ ser\'a la intersecci\'on con el eje x de la recta que une 
a $(p_1,f(p_1))$ y $(p_2,f(p_2))$.
%~ \par
Por otro lado, si $f(p_2)f(p_1) > 0$, $p_3$ ser\'a la intersecci\'on 
del eje x con la recta que pasa por $(p_0,f(p_0))$ y $(p_2,f(p_2))$.

\paragraph{}
Como $X_n$ y $X_{n-1}$ tienen distinto signo se evita la resta de dos 
n\'umeros muy parecidos obteniendo una mayor estabilidad del algoritmo. 
De la misma forma la ra\'iz est\'a siempre acotada entre dos valores de 
distinto signo (aunque es importante notar que el tamaño de este 
intervalo puede no tender a cero). Por otro lado, este m\'etodo suele 
requerir m\'as c\'alculos que el m\'etodo de la secante y no tiene la 
convergencia supralineal asegurada.
